package com.c2b.algorithm.newcoder.hash;

/**
 * <a href="https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8?tpId=295&tqId=745&ru=%2Fpractice%2Fc215ba61c8b1443b996351df929dc4d4&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj">数组中只出现一次的两个数字</a>
 *
 * <p>一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。</p>
 * <p>数据范围：数组长度2≤n≤1000，数组中每个数的大小0< val ≤1000000</p>
 * <p>要求：空间复杂度O(1)，时间复杂度O(n)</p>
 * <p>提示：输出时按非降序排列。</p>
 *
 * @author c2b
 * @since 2023/3/14 16:32
 */
public class BM0052FindNumsAppearOnce_M {

    public int[] FindNumsAppearOnce(int[] array) {
        // 两个只出现一次的数字异或运算得到的结果
        int temp = 0;
        for (int val : array) {
            temp ^= val;
        }
        // 找出这两个数字二进位表示中从低位到高位的第一个不同数的位值
        int mask = 1;
        while ((mask & temp) == 0) {
            mask <<= 1;
        }
        int a = 0;
        int b = 0;
        for (int val : array) {
            // 根据最低位的1出现的位置，对所有数字进行分组，一组为该位置为1的，一组为该位置为0的
            if ((val & mask) == 0) {
                a ^= val;
            } else {
                b ^= val;
            }
        }
        return a > b ? new int[]{b, a} : new int[]{a, b};
    }

    public static void main(String[] args) {
        BM0052FindNumsAppearOnce_M bm0052FindNumsAppearOnce_m = new BM0052FindNumsAppearOnce_M();
        for (int i : bm0052FindNumsAppearOnce_m.FindNumsAppearOnce(new int[]{1, 4, 1, 6})) {
            System.out.println(i);
        }
    }
}